package 回溯;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName _491递增子序列
 * @Description TODO
 * @Author 昝亚杰
 * @Date 2021/11/19 20:13
 * Version 1.0
 **/
public class _491递增子序列 {//有问题，未解决
    static LinkedList<Integer> result = new LinkedList<>();
    static List<List<Integer>> results = new ArrayList<>();
    static int[] used;
    public static List<List<Integer>> findSubsequences(int[] nums) {
        used = new int[nums.length];
        backTrack(nums,0);
        return results;
    }
    public static void backTrack(int [] nums, int start){
        if (start >= nums.length){
            return;
        }
        for(int i = start; i < nums.length; i++){
            if(i > 0 && nums[i] == nums[i-1] && used[i - 1] == 0){
                continue;
            }
            if(i > 0 && result.size() > 0 && nums[i] < result.getLast()){
                continue;
            }
            result.add(nums[i]);
            used[i] = 1;
            if(result.size() >= 2){
                results.add(new ArrayList<>(result));
            }
            backTrack(nums,i+1);
            result.removeLast();
            used[i] = 0;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{4,4,3,2};
        findSubsequences(nums);
    }
}
